import java.util.*;



// to find the longest repetitive string in a paragraph
public class LSD_MSD_SORT {
    public static void main(String args[]){
        String[] input = {"abc","aaa","gsx","cda","ret","caa","ers","csa","rew","aaa"};
        String[] input1 = {"aaa", "cda","caa"};

        System.out.println(threeWaySort(new ArrayList<String>(Arrays.asList(input)),0).toString());
        //System.out.println(MSD(input,0));
        System.out.println(longestRepString("hengjiaqiiqeqeqtfafofgoegvnhroinhhhleaxkhlghengjiaqisehvloivuhvgrgvgka"));

    }
    
    public static String[] LSD(String[] input,int length){
        String[] extra = new String[input.length];
        for(int mm = 0;mm<input.length;mm ++){
            extra[mm] = input[mm];
        }
        for(int kkk = length -1; kkk>=0; kkk--){
            int[] count = new int[27];
            String[] aux = new String[extra.length];
            for(int i = 0; i<extra.length; i++){
                count[extra[i].charAt(kkk) - 96]++;
            }
            for(int j = 1; j<count.length - 1; j++){
                count[j + 1] += count[j];
            }
            
            for(int m = 0; m<extra.length; m++){
                int index = extra[m].charAt(kkk) - 97;
                aux [count[index]] = extra[m];
                count[index]++;
            }
            for(int nnn= 0; nnn<aux.length;nnn++){
                extra[nnn] = aux[nnn];
            }
        }
        return extra;
    }
    
    
    public static List<String> threeWaySort(ArrayList<String> input, int index){
    		if(input.size() <=1 || index >= input.get(0).length()){
    			return input;
    		}else if(input.size() == 2){
    			if(input.get(0).charAt(index) > input.get(1).charAt(index)){
    				List<String> result = new ArrayList<String>();
    				result.add(input.get(1));
    				result.add(input.get(0));
    				return result;
    			}else{
    				return input;
    			}
    		}else{
    			char stone = input.get(0).charAt(index);
    			ArrayList<String> first = new ArrayList<String>();
    			ArrayList<String> second = new ArrayList<String>();
    			ArrayList<String> third = new ArrayList<String>();
    			for(int i = 0; i<input.size(); i++){
    				if(input.get(i).charAt(index)< stone){
    					first.add(input.get(i));
    				}else if(input.get(i).charAt(index) == stone){
    					second.add(input.get(i));
    				}else{
    					third.add(input.get(i));
    				}
    			}
    			List<String> result = new ArrayList<String>();
    			result.addAll(threeWaySort(first, index));
    			result.addAll(threeWaySort(second, index +1));
    			result.addAll(threeWaySort(third, index));
    			return result;
    		}
    }

    
    public static List<String> MSD(String[] input, int index){
    		List<String> result = MSDHelper(Arrays.asList(input), index);
    		return result;
    }
    
    public static List<String> MSDHelper(List<String> input, int index){
    		if(input.size() <= 1){
    			return input;
    		}else if(index + 1 > input.get(0).length()){
    			return input;
    		}else{
    			int[] count = new int[27];
    			List<String> extra  = new ArrayList<String>(input.size());
    			for(int mm = 0; mm<input.size();mm++){
    				extra.add("0");
    			}
    			
    			for(int i = 0; i< input.size(); i++){
    				count[input.get(i).charAt(index)-96]++;
    			}
    			int[] copy = new int[27];
    			for(int haha = 0; haha<count.length;haha++){
    				copy[haha] = count[haha];
    			}
    			for(int j = 1; j< 27; j++){
    				count[j] = count[j] + count[j -1];
    			}
    			
    			for(int k = 0; k< input.size(); k++){
    				int location = count[input.get(k).charAt(index) - 97];
    				
    				extra.set(location, input.get(k));
    				count[input.get(k).charAt(index) - 97]++;
    			}
    			List<String> result = new ArrayList<String>();
    			int lastIndex = 0;
    			
    			for(int l = 1; l < copy.length; l++){
    				if(copy[l] != 0){
	    				List<String> temp = new ArrayList<String>();
	    				for(int n = 0; n < copy[l]; n ++){
	    					temp.add(extra.get(n + lastIndex));
	    				}
	    				lastIndex = lastIndex + copy[l];

	    				result.addAll(MSDHelper(temp, index+1));
    				}
    			}
    			return result;
    		}
    	
    	
    }
    
    
    public static String longestRepString(String input){
    		int max = input.length();
    		ArrayList<String> allPossible = new ArrayList<String>();
    		for(int i = 0; i < max; i++){
    			String seg = input.substring(i);
    			for(int j = 0; j < i; j++){
    				seg += "`";
    			}
    			allPossible.add(seg);
    		}
    		List<String> result = threeWaySort(allPossible,0);
    		String maxString = "";
    		for (int j = 0; j < result.size() - 1; j++){
    			String first = result.get(j);
    			String second = result.get(j+1);
    			String common = "";
    			for(int h = 0; h< first.length(); h++){
    				if(first.charAt(h) != second.charAt(h)){
    					common = first.substring(0, h);
    					break;
    				}	
    			}
    			if(common.length() > maxString.length()){
    				maxString = common;
    			}
    		}
    		return maxString;
    	
    }
}